package study.sort;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {-9, 78, 0, 23, -567, 70};

        quickSort(arr, 0, arr.length - 1);

        System.out.println("排序后：" + Arrays.toString(arr));

    }

    public static void quickSort(int[] arr, int left, int right) {
        int lIndex = left;
        int rIndex = right;
        //中间值
        int middleValue = arr[(left + right) / 2];

        int temp = 0;

        //先处理左边
        //{-9, 78, 0, 23, -567, 70}
        //左边{-9, 78}
        while (lIndex < rIndex){

            //遍历左边的值
            //小于中间值的话就让lIndex + 1
            while (arr[lIndex] < middleValue){
                lIndex++;
            }

            //遍历右边的值
            //小于中间值的话就让rIndex - 1
            while (arr[rIndex] > middleValue){
                rIndex--;
            }

            //当lIndex >= rIndex
            if (lIndex >= rIndex){
                break;
            }

            //当满足上述条件时，进行交换
            temp = arr[lIndex];
            arr[lIndex] = arr[rIndex];
            arr[rIndex] = temp;

            //如果交换过后，发现arr[lIndex] == middleValue，就将rIndex--
            if (arr[lIndex] == middleValue){
                rIndex--;
            }

            //如果交换过后，发现arr[lIndex] == middleValue，就将lIndex++
            if (arr[rIndex] == middleValue){
                lIndex++;
            }

        }

        if (lIndex == rIndex){
            lIndex++;
            rIndex--;
        }
        //排序左边的数字，向左递归
        if (left < rIndex){
            quickSort(arr, left, rIndex);
        }

        //排序右边的数字，向右递归
        if (right > lIndex ){
            quickSort(arr, lIndex, right);
        }

    }


}
